A conventional database system uses a datastore to persistently store data pages, and a cache to provide fast access to the data pages. For example, in response to a request to access a data page, the data page is loaded from the datastore into the cache, and may thereafter be accessed from and/or modified within the cache.
The datastore may include a tree of converter pages. Converter pages at the lowest level of the tree map logical page numbers of data pages to locations of the datastore at which the data pages are stored. The tree of converter pages is loaded into the cache upon initialization of the database system, and the cached converter pages are used to determine the location of a particular page within the datastore in response to a request to access the particular page.
At specified times (e.g., when the cache reaches a particular percentage of full capacity, when a savepoint is initiated, etc.), modified data pages from the cache are written back to the datastore. A “shadow paging” system may be employed, in which the original unmodified data page remains designated as a “last known good” page in the datastore and the modified data page is written to a new location in the datastore. The converter pages are therefore modified within the cache once a modified data page is saved to a new location of the datastore. The modified converter pages are written to the datastore at the end of a savepoint, after all modified data pages are written, and are written to locations which are different from the locations of the last versions of the converter pages.
In order to determine the location of a particular page in the datastore, the cached tree of converter pages is traversed from its root level to a corresponding converter page located at the lowest level of the tree. For example, a converter page at the root level may identify one or more converter pages located at a next level of the tree. A hashmap, which was created when the converter pages were loaded into the cache, is consulted to determine the cache addresses of the identified next-level converter pages in the tree. The process repeats to traverse the levels of the tree until the address of a lowest-level converter page corresponding to the desired logical page number is determined.
As described above, a modified data page is eventually written from the cache to the datastore. After writing such a page, its associated lowest-level converter page is modified in order to point to the location at which the modified data page is written, and all ancestor pages of the modified converter page are also modified. Identification of each of these to-be-modified converter pages also requires a distinct hash map transaction as described above.